package com.shuang.stackAndQueue2;

import java.util.ArrayDeque;
import java.util.Queue;

public class MyStack {
    //方法一：两个队列实现栈 队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1

    //方法二： 一个队列实现栈 一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了


    //方法一：

    // //保证队列1的输出顺序与栈相同 队列2用于辅助
    // Queue<Integer> q1;
    // Queue<Integer> q2;

    // public MyStack() {

    //     q1 = new ArrayDeque<>();
    //     q2 = new ArrayDeque<>();

    // }

    // public void push(int x) {
    //     //在加入元素时先将q1中的元素依次输出到q2，然后将新加入的元素加入到q1中，再将q2中的元素依次输入到q1
    //     while (q1.size() > 0) {
    //         q2.add(q1.poll());
    //     }

    //     q1.add(x);

    //     while (q2.size() > 0) {
    //         q1.add(q2.poll());
    //     }

    //     //上述过程做完相当于q1的输出顺序与栈的输出顺序是一样的了，下面直接使用q1即可
    // }

    // public int pop() {
    //     return q1.poll();
    // }

    // public int top() {
    //     return q1.peek();
    // }

    // public boolean empty() {
    //     return q1.isEmpty();
    // }

    //方法二：
    Queue<Integer> q1;

    public MyStack() {
        q1 = new  ArrayDeque<>();

    }

    public void push(int x) {
        //每 输入 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
        q1.add(x);

        int size = q1.size();
        while (size > 1) {
            q1.add(q1.poll());
            size--;
        }

        //上述过程做完相当于q1的输出顺序与栈的输出顺序是一样的了，下面直接使用q1即可
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

